
package permutacionesbipartito;
import java.util.*;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.util.ArrayList;

public class Main {

   public static BiGrafo res;
    public static void main(String[] args) 
    {

        ArrayList<Node> V1=new ArrayList<Node>();
        
        Parser parser = new Parser(); 
        File fileIn = new File("Tp3.in");
        File fileOut = new File("Tp3.out");
        File cantOp = new File("cantOp.out");
        BiGrafo big = new BiGrafo();
        FileReader frIn = null;
        FileWriter fwOut = null;
        FileWriter fwCantOp = null;

        try {
                frIn = new FileReader(fileIn);
                BufferedReader in = new BufferedReader(frIn);
                fwOut = new FileWriter(fileOut);
                BufferedWriter out = new BufferedWriter(fwOut);
                fwCantOp = new FileWriter(cantOp);
                BufferedWriter outOp = new BufferedWriter(fwCantOp); 


                Parser.levantoDatos(parser,in,out,outOp,big);
                //Constructiva cons = new Constructiva();
                //int cruces = cons.ContructivaAlgo(big);
                big.cantidadCruces();
                System.out.println(permuto(big.iv1/*V1*/, 0, 1,true, 0, big.v1/*fijos1*/, false, big.iv2/*v2*/, big.v2/*fijos2*/, V1));			
                res.cantidadCruces();
                System.out.print("fin");
		}
            catch (IOException e) 
            {
                System.out.println("NO SE PUDO LEER EL ARCHIVO");
                e.printStackTrace();
            }
            finally 
            {
		try 
                {
                    if ( frIn != null )
                            frIn.close();
                }
                catch (IOException e) 
                {
                    System.out.println("Error al cerrar el archivo de entrada");
                }
                try 
                {
                        if ( fwCantOp != null )
                                fwCantOp.close();
                }
                catch (IOException e) 
                {
                        System.out.println("Error al cerrar el archivo de salida");
                }
                try 
                {
                        if ( fwOut != null )
                                fwOut.close();
                }
                catch (IOException e) 
                {
                        System.out.println("Error al cerrar el archivo grafo");
                }

            }
    }
    public static int permuto(ArrayList<Node> arrV1, int dsd, int hst, boolean b, int veces, ArrayList<Node> fijosV1, boolean esV2, ArrayList<Node> arrV2, ArrayList<Node> fijosV2, ArrayList<Node> V1)
    {
        int i=dsd;
        Node aux;
        while (i<hst+1)
        {
            if ((hst-dsd)==1)
            {
                Node tmp;
                tmp=arrV1.get(hst);
                arrV1.set(hst, arrV1.get(dsd));
                arrV1.set(dsd, tmp);
                i++;
                // INTERCALA CON LOS ELEMENTOS FIJOS CON LA PERMUTACION Y CUENTA LA CANTIDAD DE CORTES
                if (esV2)
                {
                    ArrayList<Node> caso= new ArrayList<Node>();
                    int j=0;
                    int k=0;
                    while (j<fijosV1.size())
                    {
                        caso.add(j, fijosV1.get(j));
                        j++;
                    }
                    while (k<arrV1.size())
                    {
                        caso.add(j, arrV1.get(k));
                        j++;
                        k++;
                    }
                    int cantDsps=fijosV1.size();
                    if (cantDsps==0) // Esto es para que si la cantidad es cero no pase un -1 a intercalar
                        cantDsps++;
                    //Genero el grafo y verifico los cortes, si son menores al que tenia lo guardo
                    if (res==null)
                    {
                        res = new BiGrafo(new ArrayList<Node>(V1), new ArrayList<Node>(caso));
                    }
                    else
                    {
                        BiGrafo bg = new BiGrafo(V1, caso);
                        if (bg.cantidadCruces()< res.cantidadCruces())
                            res= new BiGrafo(new ArrayList<Node>(V1), new ArrayList<Node>(caso));
                    }
                    intercalar(caso, 0, cantDsps-1, arrV2, fijosV2, true, V1);
                }
                else
                {
                    ArrayList<Node> caso= new ArrayList<Node>();
                    int j=0;
                    int k=0;
                    while (j<fijosV1.size())
                    {
                        caso.add(j, fijosV1.get(j));
                        j++;
                    }
                    while (k<arrV1.size())
                    {
                        caso.add(j, arrV1.get(k));
                        j++;
                        k++;
                    }
                    k=permuto(arrV2, 0, arrV2.size()-1, true, 0, fijosV2, true, arrV1, fijosV1, caso);
                    int cantDsps=fijosV1.size();
                    if (cantDsps==0) // Esto es para que si la cantidad es cero no pase un -1 a intercalar
                        cantDsps++;
                    intercalar(caso, 0, cantDsps-1, arrV2, fijosV2, false, caso);
                }
                veces++;
            }
            else
            {
                ArrayList<Node> ref= new ArrayList<Node>();
                int j=0;
                while (j<arrV1.size())
                {
                    ref.add(j, arrV1.get(j));
                    j++;
                }
                if (!esV2)
                {
                    veces=permuto(ref, dsd+1, hst, false, veces, fijosV1, false, arrV2, fijosV2, V1);                    
                }
                else
                {
                    veces=permuto(ref, dsd+1, hst, false, veces, fijosV1, true, arrV2, fijosV2, V1);
                }
                i++;
                if (i<hst+1)
                {
                    aux=arrV1.get(dsd);
                    arrV1.set(dsd, arrV1.get(i));
                    arrV1.set(i, aux);
                }
            }
        }
        return veces;
    }
    public static ArrayList<Node> intercalar(ArrayList<Node> instancia, int posicion, int cantDsps, ArrayList<Node> instanciaV2, ArrayList<Node> fijosV2, boolean esV2, ArrayList<Node> vieneDeV1)
    {
        boolean primero=true;
        int pInicial,k; // contadores
        pInicial=posicion+1;
        k=posicion;
        Node t;
        ArrayList<Node> original= new ArrayList<Node>();
        if (!esV2)
        {
            while (posicion<(instancia.size()-cantDsps-1))
            {
                if (cantDsps>0)
                {
                    instancia=intercalar(instancia, posicion+1, cantDsps-1, instanciaV2, fijosV2, esV2, vieneDeV1);
                    t=instancia.get(posicion);
                    instancia.set(posicion, instancia.get(posicion+1));
                    instancia.set(posicion+1, t);
                    if (primero)
                    {
                        original = new ArrayList<Node>(instancia);
                        primero=false;
                    }
                    int veces=permuto(instanciaV2, 0, instanciaV2.size()-1, true, 0, fijosV2, true, instanciaV2, fijosV2, instancia);
                    posicion++;
                }
                else
                {
                    t=instancia.get(posicion);
                    instancia.set(posicion, instancia.get(posicion+1));
                    instancia.set(posicion+1, t);
                    if (primero)
                    {
                        original = new ArrayList<Node>(instancia);
                        primero=false;
                    }
                    int veces=permuto(instanciaV2, 0, instanciaV2.size()-1, true, 0, fijosV2, true, instanciaV2, fijosV2, instancia);
                    posicion++;
                }
            }
        }
        else
        {
            while (posicion<(instancia.size()-cantDsps-1))
            {
                if (cantDsps>0)
                {
                    instancia=intercalar(instancia, posicion+1, cantDsps-1, instanciaV2, fijosV2, esV2, vieneDeV1);
                    t=instancia.get(posicion);
                    instancia.set(posicion, instancia.get(posicion+1));
                    instancia.set(posicion+1, t);
                    if (primero)
                    {
                        original = new ArrayList<Node>(instancia);
                        primero=false;
                    }
                    //Genero el grafo y verifico los cortes, si son menores al que tenia lo guardo
                    if (res==null)
                    {
                        res = new BiGrafo(new ArrayList<Node>(vieneDeV1), new ArrayList<Node>(instancia));
                    }
                    else
                    {
                        BiGrafo bg = new BiGrafo(vieneDeV1, instancia);
                        if (bg.cantidadCruces()< res.cantidadCruces())
                            res= new BiGrafo(new ArrayList<Node>(vieneDeV1), new ArrayList<Node>(instancia));
                    }
                    posicion++;
                }
                else
                {
                    t=instancia.get(posicion);
                    instancia.set(posicion, instancia.get(posicion+1));
                    instancia.set(posicion+1, t);
                    if (primero)
                    {
                        original = new ArrayList<Node>(instancia);
                        primero=false;
                    }
                    //Genero el grafo y verifico los cortes, si son menores al que tenia lo guardo
                    if (res==null)
                    {
                        res = new BiGrafo(new ArrayList<Node>(vieneDeV1), new ArrayList<Node>(instancia));
                    }
                    else
                    {
                        BiGrafo bg = new BiGrafo(vieneDeV1, instancia);
                        if (bg.cantidadCruces()< res.cantidadCruces())
                            res=new BiGrafo(new ArrayList<Node>(vieneDeV1), new ArrayList<Node>(instancia));
                    }
                    posicion++;
                }
            }
        }
        return original;
    }
}
